1. Field of Invention
This invention relates to digital signal processing and more particularly it relates to methods and apparatus for generating the necessary address sequences for performing butterfly functions of various transforms known collectively as fast Fourier transforms (FFT) for a preselected number of points. The class of processes generally known as discrete Fourier transforms (DFT) relates to signals stored at least temporarily in sampled digital form in a digital memory.
Fast Fourier transforms are a class of processes which are capable of performing Fourier transformation of signals with considerably fewer multiplication operations than normally is required for Fourier transformation. For example, direct evaluation of a discrete Fourier transform on N number of points requires N.sup.2 complex multiplications and additions. A fast Fourier transform requires only (N/2) log.sub.2 N number of computations. For an N equal to 1024 points, this represents a computational savings of 99 percent.
There are two classes of fast Fourier transforms, decimation in time and decimation in frequency. Each class has many modifications. The fast Fourier transform is characterized by a large number of repetitive sequential multiplications of complex numbers (i.e., having real and imaginary parts) in short loops.
2. Description of the Prior Art
In the past, the identification of the particular points to be operated on in an FFT has generally required the generation of an address sequence locked into the size of the specific transform to be performed. Various computer program-implemented schemes are known which are generally so slow as to preclude real time applications. Hence, means for generating the address sequence for relatively high-speed applications have heretofore been essentially fixed discrete hardware implementations. What is needed is an address sequencer for generalized applications capable of generating addresses of stored data of essentially any modification of the classes of fast Fourier transforms for use in high-speed, e.g., real time, applications.
Hardware FFT address sequence generator structures are known for generating FFT addresses of arbitrary size. One prior art address generator, for example, has been suggested for use by TRW of Los Angles, Calif. in connection with its high-speed multipliers. The address sequencer comprises approximately a dozen individual components, including a complex array of various counters, multiplexers and index generating circuits. What is desired is a technique for address sequencing which can be incorporated into an apparatus as a single integrated circuit.